<?php
	//------------------------------------------------------------------------------------------------------------------
	//Preprocesar la expresion regular para escribir un + para identificar la concatenación y sutituir ? por (|E)
	function preprocesar($oldRegex,$myoperadores){
		
		$newRegex = '';	
		$ultimo = $oldRegex[0];
		$newRegex = $newRegex.$ultimo;
		
		for ($i = 1; $i < strlen($oldRegex); $i++){
			//si es un parentesis que cierra, un asterisco o una letra seguido de una letra o de un parentesis cerrado, debe haber un +
			if ( (($ultimo == ')') || ($ultimo == '*') || ($ultimo == '+') || !in_array($ultimo,$myoperadores)) && (!in_array($oldRegex[$i],$myoperadores) || $oldRegex[$i]=='(')){
				$newRegex = $newRegex.'.';
				$ultimo = $oldRegex[$i];
			}
			//Si es Operador Integorración 
			else if($oldRegex[$i]=='?'){
				$newRegex = $newRegex.'|';
				$ultimo = '&';				
			}
			//Nada de lo anterior
			else{
				$ultimo = $oldRegex[$i];			
			}
			$newRegex = $newRegex.$ultimo;

		}		
		return $newRegex;
	}
	
	//------------------------------------------------------------------------------------------------------------------	
	//Determinar si un operador es Mayor o Igual
	function opMayorIgual($a,$b)
	{
		$jerarquia = '*+.|';
		$posA = strpos($jerarquia,$a);
		$posB = strpos($jerarquia,$b);
		if ($a>=$b)
			return true;
		else
			return false;
	}
	
	//------------------------------------------------------------------------------------------------------------------	
	//Infix a Postfix
	function infixPostfix($infix,$myAlfabeto){
		$opStack = new Stack();
		$postfix = '';
	
		for ($i = 0; $i < strlen($infix); $i++){
			
			//Si es Cerradura Kleene o cerradura Positiva (Unario)
			if (($infix[$i] == '*') || ($infix[$i] == '+')){
				$postfix = $postfix.$infix[$i];			
			}
			
			//Si es un operador Concatenación o Unión (Binario)
			else if ($infix[$i]=='.' || $infix[$i]=='|'){
				while( !$opStack->is_empty() && $opStack->top()!='(' )
				{
					if ( opMayorIgual($opStack->top(), $infix[$i]) )
					{
						$postfix = $postfix.$opStack->top();
						$opStack->pop();
					}
					else break;
				}
				$opStack->push($infix[$i]);			
				}
			
			//Si es paréntesis abierto
			else if ( $infix[$i]=='(' )
			{
				$opStack->push($infix[$i]);
			}
			
			//Si es un paréntesis cerrado
			else if ( $infix[$i]==')' )
			{
				while ( !$opStack->is_empty() && $opStack->top()!='(' )
				{
					$postfix = $postfix.$opStack->top();
					$opStack->pop();
				}
				if ( !$opStack->is_empty() ) $opStack->pop();
			}
			
			//Elemento del alfabeto
			else if ( in_array($infix[$i],$myAlfabeto) )
			{
				$postfix = $postfix.$infix[$i];
			}						
		}

		while ( !$opStack->is_empty() )
			{
				$postfix = $postfix.$opStack->top();
				$opStack->pop();
			}		
		
		return $postfix;
	}
	
	//------------------------------------------------------------------------------------------------------------------
	//Evaluaremos la Regex que ya está en Postfix y crearemos las funciones de transición cuando recorramos la expresión.
	function evaluarPostfix($myRegex,$myAlfabeto){
		//Evaluador
		$evaluador = new Stack();
		$evaluacion = '';
		for ($i = 0; $i < strlen($myRegex); $i++){
			
			//Si es un simbolo del alfabeto 
			if ( in_array($myRegex[$i],$myAlfabeto) ){	
				$evaluador->push($myRegex[$i]);
			}
			
			//Concatenacion y Union
			else if (($myRegex[$i] == '.') || ($myRegex[$i] == '|')){	
				$temp1 = $evaluador->top();
				$evaluador->pop();
				$temp2 = $evaluador->top();
				$evaluador->pop();
				$retorno =  $temp2.$myRegex[$i].$temp1;
				$evaluador->push($retorno);		
			}
			//Cerraduras de Klein y Postiva
			else if (($myRegex[$i] == '*') || ($myRegex[$i] == '+')){	
				$temp1 = $evaluador->top();
				$evaluador->pop();
				$retorno = $temp1.$myRegex[$i];
				$evaluador->push($retorno);
			}	
		}
		$evaluacion = $evaluador->top();
		$evaluador->pop();
		return $evaluacion;
	
	};

	//------------------------------------------------------------------------------------------------------------------
	//Recorrer la expresion regular para identificar cuales operadores está usando y cuales son los simbolos del alfabeto
	function getAlfabeto($myRegex,$palabrasReservadas){
		$alfabeto = array();
		for ($i = 0; $i < strlen($myRegex); $i++){
			if ( (in_array($myRegex[$i],$palabrasReservadas) == false) && (in_array($myRegex[$i],$alfabeto) == false ) )
				$alfabeto[] =  $myRegex[$i];
		}
		return $alfabeto;
	}
	
	//------------------------------------------------------------------------------------------------------------------
	//Recorrer la expresion regular para identificar cuales operadores está usando y cuales son los simbolos del alfabeto
	function getPalabrasReservadasEnUso($myRegex,$palabrasReservadas){
		$myPalabrasReservadasEnUso = array();
		for ($i = 0; $i < strlen($myRegex); $i++){
			if ( (in_array($myRegex[$i],$palabrasReservadas))  && (in_array($myRegex[$i],$myPalabrasReservadasEnUso) == false ) )
				$myPalabrasReservadasEnUso[] =  $myRegex[$i];	
		}
		return $myPalabrasReservadasEnUso;
	}
	
?>